package com.tlvip.arithmetic.ch07;

/**
 * <p>description：希尔排序</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/26/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class ShellSort {
    // 思想：在插入排序基础上进行优化，尽最大努力执行break
    // 每次折半对比，a[i] 与 a[i + n]进行对比
    // 第一次 n = length / 2
    // 第二次 n = length / 4
    // ......
    // 第n次 n = 1
    public static void main(String[] args) {
        sellSortOfTeacher();
    }

    public static void sellSortOfMine() {
        int data[] = {9, 8, 7, 0, 1, 2, 3};
        int n = data.length;
        int count = 0;
        while (n > 0) {
            n = n / 2;
            for (int i = 0; i <= data.length; i++) {
                count++;
                if ((i + n < data.length) && (data[i] > data[i + n])) {
                    int temp = data[i];
                    data[i] = data[i + n];
                    data[i + n] = temp;
                }
            }
        }
        print(data);
        System.out.println("总共执行:" + count + "次");
    }

    /**
     * 提供的样例
     * 思想：折半对比并交换，多次折半直到n / 2 = 1为止
     * 不稳定的排序方法
     */
    public static void sellSortOfTeacher() {
        int a[] = {11, 9, 8, 7, 0, 1, 2, 3, 10};
        int n = a.length;
        for (int add = n / 2; add >= 1; add /= 2) {
            for (int i = add; i < n; i++) {
                int data = a[i];
                int j = i - add;
                for (; j >= 0; j -= add) {
                    if (a[j] > data) {
                        a[j + add] = a[j];
                    } else {
                        break;
                    }
                }
                a[j + add] = data;
            }
        }
        print(a);
    }

    public static void print(int a[]) {
        for (int i : a) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }
}
